package leetcode.N301_N400;

import java.util.Stack;

/**
 * @author 歪大哥😁
 * @date 2020-07-27.
 * 给定一个经过编码的字符串，返回它解码后的字符串。
 *
 * 编码规则为: k[encoded_string]，表示其中方括号内部的 encoded_string 正好重复 k 次。注意 k 保证为正整数。
 *
 * 你可以认为输入字符串总是有效的；输入字符串中没有额外的空格，且输入的方括号总是符合格式要求的。
 *
 * 此外，你可以认为原始数据不包含数字，所有的数字只表示重复的次数 k ，例如不会出现像 3a 或 2[4] 的输入。
 *
 *  
 *
 * 示例 1：
 *
 * 输入：s = "3[a]2[bc]"
 * 输出："aaabcbc"
 * 示例 2：
 *
 * 输入：s = "3[a2[c]]"
 * 输出："accaccacc"
 * 示例 3：
 *
 * 输入：s = "2[abc]3[cd]ef"
 * 输出："abcabccdcdcdef"
 * 示例 4：
 *
 * 输入：s = "abc3[cd]xyz"
 * 输出："abccdcdcdxyz"
 *
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode-cn.com/problems/decode-string
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 */
public class N394 {


    public static void main(String[] args) {
        String s = "4[a]10[asb]";
        String s2 = "3[a2[c]]";
        System.out.println(decodeString(s2));
    }

    public static String decodeString(String s) {
        int sl = s.length();
        if (sl == 0) {
            return "";
        }
        StringBuilder all = new StringBuilder();
        StringBuilder charReader = new StringBuilder();
        StringBuilder numReader = new StringBuilder();
        char left = '[';
        char right = ']';
        Stack<Character> stack = new Stack<>();
        for (int i = 0; i < sl; i++) {
            char currentChar = s.charAt(i);
            if (currentChar != right) {
                stack.push(currentChar);
                continue;
            }
            // 解析并拼接
            for (char n = stack.pop(); n != left; n = stack.pop()) {
                charReader.append(n);
            }
            charReader.reverse();

            char b = stack.pop();
            while (b != right) {
                numReader.append(b);
                if (stack.empty()) {
                    break;
                }
                b = stack.pop();
                // 如果是嵌套 则b有可能是字母 若b是字母 则退出数字解析
                if (b < '1' || b > '9' ) {
                    stack.push(b);
                    break;
                }
            }
            int times = Integer.valueOf(numReader.reverse().toString());

            for (int j = 0; j < times; j++) {
                all.append(charReader);
            }

            charReader.setLength(0);
            numReader.setLength(0);
        }
        return all.toString();
    }
}
